package cn.bellychang.wangzheng.binarysearchtree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author ChangLiang
 * @date 2021/2/7
 */
public class BST<E extends Comparable<E>> {

    private TreeNode root;

    public List<E> inOrderTraversal() {
        List<E> list = new ArrayList<>();
        inOrderTraversal(list, root);
        return list;
    }

    private void inOrderTraversal(List<E> list, TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        if (treeNode.left == null && treeNode.right == null) {
            list.add(treeNode.val);
            return;
        }
        inOrderTraversal(list, treeNode.left);
        list.add(treeNode.val);
        inOrderTraversal(list, treeNode.right);
    }

    public void removeAll(E val) {

        // 需要记录其父节点
        TreeNode curr = root;
        TreeNode parent = null;

        while (curr != null) {

            // 先找到第一个要删除的内容
            if (curr.val.compareTo(val) < 0) {
                parent = curr;
                curr = curr.right;
            } else if (curr.val.compareTo(val) > 0) {
                parent = curr;
                curr = curr.left;
            } else {
                if (parent == null) {
                    // 说明删除的是root
                    if (root.left == null && root.right == null) {
                        root = null;
                    } else if (root.left == null) {
                        root = root.right;
                    } else if (root.right == null) {
                        root = root.left;
                    } else {
                        TreeNode min = findMinFromRightTree(root);
                        min.left = root.left;
                        min.right = root.right;
                        root = min;
                    }
                }else{
                    if (curr.left == null && curr.right == null) {
                        if (parent.val.compareTo(val) < 0) {
                            parent.right = null;
                        } else {
                            parent.left = null;
                        }
                    } else if (curr.left == null) {
                        if (parent.val.compareTo(val) < 0) {
                            parent.right = curr.right;
                        } else {
                            parent.left = curr.right;
                        }
                    } else if (curr.right == null) {
                        if (parent.val.compareTo(val) < 0) {
                            parent.right = curr.left;
                        } else {
                            parent.left = curr.left;
                        }
                    } else {
                        // 如果其包含两个子节点 那么需要找到其右子树的最小值
                        TreeNode minLeft = findMinFromRightTree(curr);
                        if (parent.val.compareTo(minLeft.val) < 0) {
                            parent.right = minLeft;
                        } else {
                            parent.left = minLeft;
                        }
                        minLeft.left = curr.left;
                        minLeft.right = curr.right;

                        // 删除之后 要回到parent 因为移动过来的TreeNode可能仍旧等于val
                        curr = parent;
                    }
                }
            }
        }

    }

    public void remove(E val) {

        // 需要记录其父节点
        TreeNode curr = root;
        TreeNode parent = null;

        while (curr != null && curr.val.compareTo(val) != 0) {
            parent = curr;
            if (curr.val.compareTo(val) < 0) {
                curr = curr.right;
            } else {
                curr = curr.left;
            }
        }
        // 没找到
        if (curr == null) {
            return;
        }
        if (parent == null) {
            // 说明要删除的是根节点
            if (root.left == null && root.right == null) {
                root = null;
            } else if (root.left == null) {
                root = root.right;
            } else if (root.right == null) {
                root = root.left;
            } else {
                TreeNode minLeft = findMinFromRightTree(root);
                minLeft.left = root.left;
                minLeft.right = root.right;
                root = minLeft;
            }
        } else {
            if (curr.left == null && curr.right == null) {
                if (parent.val.compareTo(val) < 0) {
                    parent.right = null;
                } else {
                    parent.left = null;
                }
            } else if (curr.left == null) {
                if (parent.val.compareTo(val) < 0) {
                    parent.right = curr.right;
                } else {
                    parent.left = curr.right;
                }
            } else if (curr.right == null) {
                if (parent.val.compareTo(val) < 0) {
                    parent.right = curr.left;
                } else {
                    parent.left = curr.left;
                }
            } else {
                // 如果其包含两个子节点 那么需要找到其右子树的最小值
                TreeNode minLeft = findMinFromRightTree(curr);
                if (parent.val.compareTo(minLeft.val) < 0) {
                    parent.right = minLeft;
                } else {
                    parent.left = minLeft;
                }
                minLeft.left = curr.left;
                minLeft.right = curr.right;
            }
        }
    }

    private TreeNode findMinFromRightTree(TreeNode treeNode) {
        TreeNode min = treeNode.right;
        TreeNode minParent = treeNode;
        if (min.left == null) {
            minParent.right = min.right;
            return min;
        }
        while (min.left != null) {
            minParent = min;
            min = min.left;
        }
        // 注意这里要连接起来
        minParent.left = min.right;
        return min;
    }

    public void addRecursive(E val) {
        if (root == null) {
            root = new TreeNode(val);
            return;
        }
        addRecursive(root, val);
    }

    private TreeNode addRecursive(TreeNode treeNode, E val) {
        if (treeNode == null) {
            return new TreeNode(val);
        }
        if (treeNode.val.compareTo(val) <= 0) {
            treeNode.right = addRecursive(treeNode.right, val);
        } else {
            treeNode.left = addRecursive(treeNode.left, val);
        }
        return treeNode;
    }

    public List<TreeNode> getAll(E val) {
        List<TreeNode> list = new ArrayList<>();
        // 首先要找到第一个val 然后遍历其右子树
        TreeNode temp = root;
        while (temp != null) {
            if (temp.val.compareTo(val) == 0) {
                list.add(temp);
                temp = temp.right;
            } else if (temp.val.compareTo(val) < 0) {
                temp = temp.right;
            } else {
                temp = temp.left;
            }
        }
        return list;
    }


    public TreeNode getRecursive(E val) {
        return getRecursive(root, val);
    }

    private TreeNode getRecursive(TreeNode treeNode, E val) {
        if (treeNode == null) {
            return null;
        }
        if (treeNode.val.compareTo(val) == 0) {
            return treeNode;
        } else if (treeNode.val.compareTo(val) > 0) {
            // 说明要在左子树中查找
            return getRecursive(treeNode.left, val);
        } else {
            return getRecursive(treeNode.right, val);
        }
    }


    private int getHeight(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        return Math.max(getHeight(treeNode.left), getHeight(treeNode.right)) + 1;
    }

    private void printSpace(long size) {
        for (int i = 0; i < size; i++) {
            System.out.print(" ");
        }
    }

    public void printBST() {
        if (root == null) {
            return;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        // 表示还有几个要打印
        int currSize = queue.size();
        TreeNode poll;
        int length = 1;
        int tempLength = 0;
        while ((poll = queue.poll()) != null) {
            System.out.print(poll + "   ");
            tempLength++;

            if (poll.val != null) {
                currSize--;
            }

            if (poll.left != null) {
                queue.offer(poll.left);
                currSize++;
            } else {
                queue.offer(new TreeNode(null));
            }

            if (poll.right != null) {
                queue.offer(poll.right);
                currSize++;
            } else {
                queue.offer(new TreeNode(null));
            }

            if (length == tempLength) {
                System.out.println();
                length = length * 2;
                tempLength = 0;
                if (currSize == 0) {
                    break;
                }
            }
        }

    }

    /**
     * 加入分隔 效果不好
     */
    public void printBST2() {
        int maxHeight = getHeight(root);
        long maxLength = Math.round(Math.pow(2, maxHeight)) * 2;
        int height = 1;
        if (root == null) {
            return;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        // 表示还有几个要打印
        int currSize = queue.size();
        TreeNode poll;
        int length = 1;
        int tempLength = 0;
        while ((poll = queue.poll()) != null) {
            long printSize;

            if (height == maxHeight) {
                printSize = maxLength / (length + 1);
            } else {
//                printSize = Math.min(maxLength / (length * 2 + 1) * 3 / 2, maxLength / (length * 2) + 1);
                printSize = maxLength / (length * 2 + 1) * 3 / 2;
            }

            printSpace(printSize);
            System.out.print(poll);
            tempLength++;

            if (poll.val != null) {
                currSize--;
            }

            if (poll.left != null) {
                queue.offer(poll.left);
                currSize++;
            } else {
                queue.offer(new TreeNode(null));
            }

            if (poll.right != null) {
                queue.offer(poll.right);
                currSize++;
            } else {
                queue.offer(new TreeNode(null));
            }

            if (length == tempLength) {
                System.out.println();
                length = length * 2;
                tempLength = 0;
                if (currSize == 0) {
                    break;
                }
                height++;
            }
        }

    }

    class TreeNode {
        private E val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode(E val) {
            this.val = val;
        }

        public E getVal() {
            return val;
        }

        @Override
        public String toString() {
            if (val == null) {
                return "N";
            }
            return val.toString();
        }
    }
}
